package com.practice.suffixtree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Set;


public class ShortestUniqueSubstring {
	public ArrayList<String> find(String str) {
		TrieNode root = new TrieNode();
		buildSuffix(root, str);
		HashMap<TrieNode, String> prev = new HashMap<TrieNode, String>();
		HashMap<TrieNode, String> cur = new HashMap<TrieNode, String>();
		ArrayList<String> result = new ArrayList<String>();
		prev.put(root, "");
		
		while(result.isEmpty()) {
			for (TrieNode node : prev.keySet()) {
				String s = prev.get(node);
				for (Character c : node.keys()) {
					TrieNode child = node.get(c);
					String childStr = s + c;
					if (child.isUnique()) result.add(childStr);
					cur.put(child, childStr);
				}
			}
			prev.clear();
			prev.putAll(cur);
			cur.clear();
		}
		
		return result;
	}
	
	private void buildSuffix(TrieNode root, String str) {
		char[] c = str.toCharArray();
		for (int i=c.length-1; i>=0; i--) {
			TrieNode parent = root;
			for (int j=0; j<c.length-i; j++) {
				parent = parent.addChild(c[i+j]);
			}
		}
	}
	
	private class TrieNode {
		private HashMap<Character, TrieNode> 	map;
		private int								count;
		
		public TrieNode() {
			map = new HashMap<Character, TrieNode>();
		}
		
		public TrieNode addChild(char c) {
			if (!map.containsKey(c)) {
				map.put(c, new TrieNode());
			}
			TrieNode child = map.get(c);
			child.increase();
			return child;
		}
		
		public boolean isUnique() {
			return count == 1;
		}
		
		public Set<Character> keys() {
			return map.keySet();
		}
		
		public TrieNode get(char c) {
			return map.get(c);
		}
		
		public void increase() {
			count++;
		}
	}
}
